package com.Oct_Eighteen;


/**
 * 563. 二叉树的坡度
 * 给你一个二叉树的根节点 root ，计算并返回 整个树 的坡度 。
 *
 * 一个树的 节点的坡度 定义即为，该节点左子树的节点之和和右子树节点之和的 差的绝对值 。如果没有左子树的话，左子树的节点之和为 0 ；没有右子树的话也是一样。空结点的坡度是 0 。
 *
 * 整个树 的坡度就是其所有节点的坡度之和。
 *
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/binary-tree-tilt
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * 2022/10/19 00:07
 */

public class Solution563 {

    int res=0;

    public int findTilt(TreeNode root) {
        dfs(root);
        return res;
    }

    int dfs(TreeNode root){
        if (root==null) return 0;
        int sumLeft=dfs(root.left);
        int sumRight=dfs(root.right);
        res+=Math.abs(sumLeft-sumRight);
        return root.val+sumLeft+sumRight;
    }

    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

}
